import gmpy2
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from hashlib import sha256
from Crypto.Util.number import long_to_bytes

# Given values from the output
r1 = 11455446275324978121918764201975007376236576456980676251003353868423934779741
r2 = 11455446275324978121918764201975007376236576456980676251003353868423934779741
s1 = 40939314972385973234538799073526528418921185412931089406906904671430814294251
s2 = 20521265832237322311837491925934175279870547563516618597235100170259508682349
z1 = 86373733089658748931377346977504497606857910789811212034370600969224209571891
z2 = 114906325375159287808320541183977807561041047925384600130919891200501605749979
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141

# Step 1: Calculate `k` using the given formula
k = ((z1 - z2) * gmpy2.invert(s1 - s2, n)) % n

# Step 2: Calculate `dA` using the value of `s1` and `r1`
dA = ((s1 * k - z1) * gmpy2.invert(r1, n)) % n

# Step 3: Derive AES key from dA and decrypt the AES ciphertext
# Given encrypted AES hex string
encrypted_flag_hex = "57608ba208813e738e7a354399e77272017548f9abf0da7a179a1136cda57579720b68a3ed46d85f5997c35af18f42175f43e856a0f64d964e7ab1e8a672b689"
encrypted_flag_bytes = binascii.unhexlify(encrypted_flag_hex)

# Split IV and encrypted flag
iv = encrypted_flag_bytes[:16]
encrypted_flag = encrypted_flag_bytes[16:]

# Derive AES key
aes_key = sha256(long_to_bytes(dA)).digest()

# Decrypt AES ciphertext
cipher = AES.new(aes_key, AES.MODE_CBC, iv)
decrypted_flag_padded = cipher.decrypt(encrypted_flag)

# Remove padding
try:
    decrypted_flag = unpad(decrypted_flag_padded, AES.block_size).decode('utf-8')
except ValueError:
    decrypted_flag = "Decryption failed due to padding error."

decrypted_flag
